package pack;

public class TreeHeap 
{
	int arr[];
	
	public TreeHeap()
	{
//		int mass[] = {0,2,3,2,4,5,7,9,6,8,9,11,8,9};
		arr = new int[11];
	}
	
	private int getLeft(int i)
	{
		if(0 < 2*i && 2*i < arr.length)
			return arr[2*i];
		return 0;
	}
	
	private int getRight(int i)
	{
		if(0 < 2*i+1 && 2*i+1 < arr.length)
			return arr[2*i+1];
		return 0;
	}
	
	public int getMin()
	{
		return arr[1];
	}
	
	public void printTree()
	{
		printTree(1, 0);
	}
	
	private void printTree(int num, int level)
	{
		if(getLeft(num) != 0)
			printTree(2*num, level+1);
		
		for(int i = 0; i < level; i++)
			System.out.print("\t");
		
		System.out.println(arr[num]);
		
		if(getRight(num) != 0)
			printTree(2*num+1, level+1);
	}
	
	public void insert(int num)
	{
		int i = arr.length-1;
		
		if(arr[i] != 0)
			makeNewArray();
		else
			while(arr[i] == 0 && i > 0) i--;
		
//		System.out.println("Insert - arr[" + i + "]: " + arr[i]);
		arr[++i] = num;
		
		while(arr[i/2] > arr[i])
		{
			swap(i/2, i);
			i = i/2;
		}	
	}
	
	private void swap(int a, int b)
	{
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
	
	private void makeNewArray()
	{
		int mass[] = new int[ (int) (arr.length*3/2) ];
		for(int i = 0; i < arr.length; i++)
			mass[i] = arr[i];
		arr = mass;
	}
	
	public int removeMin()
	{
		int exitNum = arr[1];
		int i = arr.length-1;
		
		while(arr[i] == 0) i--;
		
		arr[1] = arr[i];
		arr[i] = 0;
		i = 1;
		
		while(arr[i] > getLeft(i) && getLeft(i) != 0 || arr[i] > getRight(i) && getRight(i) != 0)
			if(arr[i] > getLeft(i) && getLeft(i) != 0 && getLeft(i) < getRight(i) && getRight(i) != 0)
			{	
				swap(i, 2*i);
				i = 2*i;
			}
			else
			{
				swap(i, 2*i+1);
				i = 2*i+1;
			}
		
		return exitNum;
	}
	
	public static void main(String[] args) 
	{
		TreeHeap tree = new TreeHeap();
		
		for(int k = 0; k < 15; k++)	
			tree.insert((int)(Math.random()*10+1));
		
		tree.printTree();
		System.out.println("-------------------------------");
		
		tree.removeMin();
		tree.printTree();
	}
}
